home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nbtree / nbtpage.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  12.7 KB  |  512 lines
  1. /*
  2.  *  btpage.c -- BTree-specific page management code for the Postgres btree
  3.  *            access method.
  4.  *
  5.  *  Postgres btree pages look like ordinary relation pages.  The opaque
  6.  *  data at high addresses includes pointers to left and right siblings
  7.  *  and flag data describing page state.  The first page in a btree, page
  8.  *  zero, is special -- it stores meta-information describing the tree.
  9.  *  Pages one and higher store the actual tree data.
  10.  */
  11.  
  12. #include "tmp/c.h"
  13. #include "tmp/postgres.h"
  14.  
  15. #include "storage/bufmgr.h"
  16. #include "storage/bufpage.h"
  17. #include "storage/page.h"
  18.  
  19. #include "utils/log.h"
  20. #include "utils/rel.h"
  21. #include "utils/excid.h"
  22.  
  23. #include "access/genam.h"
  24. #include "access/ftup.h"
  25. #include "access/nbtree.h"
  26.  
  27. RcsId("$Header: /private/postgres/src/access/nbtree/RCS/nbtpage.c,v 1.15 1992/07/22 23:11:59 mao Exp $");
  28.  
  29. #define BTREE_METAPAGE    0
  30. #define BTREE_MAGIC    0x053162
  31. #define BTREE_VERSION    0
  32.  
  33. typedef struct BTMetaPageData {
  34.     uint32    btm_magic;
  35.     uint32    btm_version;
  36.     BlockNumber    btm_root;
  37.     BlockNumber    btm_freelist;
  38. } BTMetaPageData;
  39.  
  40. extern bool    BuildingBtree;
  41.  
  42. /*
  43.  *  _bt_metapinit() -- Initialize the metadata page of a btree.
  44.  */
  45.  
  46. _bt_metapinit(rel)
  47.     Relation rel;
  48. {
  49.     Buffer buf;
  50.     Page pg;
  51.     int nblocks;
  52.     BTMetaPageData metad;
  53.  
  54.     /* can't be sharing this with anyone, now... */
  55.     if (!BuildingBtree)
  56.     RelationSetLockForWrite(rel);
  57.  
  58.     if ((nblocks = RelationGetNumberOfBlocks(rel)) != 0) {
  59.     elog(WARN, "Cannot initialize non-empty btree %s",
  60.            RelationGetRelationName(rel));
  61.     }
  62.  
  63.     buf = ReadBuffer(rel, P_NEW);
  64.     pg = BufferGetPage(buf, 0);
  65.  
  66.     metad.btm_magic = BTREE_MAGIC;
  67.     metad.btm_version = BTREE_VERSION;
  68.     metad.btm_root = P_NONE;
  69.     metad.btm_freelist = P_NONE;
  70.  
  71.     bcopy((char *) &metad, (char *) pg, sizeof(metad));
  72.  
  73.     WriteBuffer(buf);
  74.  
  75.     /* all done */
  76.     if (!BuildingBtree)
  77.     RelationUnsetLockForWrite(rel);
  78. }
  79.  
  80. /*
  81.  *  _bt_checkmeta() -- Verify that the metadata stored in a btree are
  82.  *               reasonable.
  83.  */
  84.  
  85. _bt_checkmeta(rel)
  86.     Relation rel;
  87. {
  88.     Buffer metabuf;
  89.     BTMetaPageData *metad;
  90.     int nblocks;
  91.  
  92.     /* if the relation is empty, this is init time; don't complain */
  93.     if ((nblocks = RelationGetNumberOfBlocks(rel)) == 0)
  94.     return;
  95.  
  96.     metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
  97.     metad = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  98.  
  99.     if (metad->btm_magic != BTREE_MAGIC) {
  100.     elog(WARN, "What are you trying to pull?  %s is not a btree",
  101.            RelationGetRelationName(rel));
  102.     }
  103.  
  104.     if (metad->btm_version != BTREE_VERSION) {
  105.     elog(WARN, "Version mismatch on %s:  version %d file, version %d code",
  106.            RelationGetRelationName(rel),
  107.            metad->btm_version, BTREE_VERSION);
  108.     }
  109.  
  110.     _bt_relbuf(rel, metabuf, BT_READ);
  111. }
  112.  
  113. /*
  114.  *  _bt_getroot() -- Get the root page of the btree.
  115.  *
  116.  *    Since the root page can move around the btree file, we have to read
  117.  *    its location from the metadata page, and then read the root page
  118.  *    itself.  If no root page exists yet, we have to create one.  The
  119.  *    standard class of race conditions exists here; I think I covered
  120.  *    them all in the Hopi Indian rain dance of lock requests below.
  121.  *
  122.  *    We pass in the access type (BT_READ or BT_WRITE), and return the
  123.  *    root page's buffer with the appropriate lock type set.  Reference
  124.  *    count on the root page gets bumped by ReadBuffer.  The metadata
  125.  *    page is unlocked and unreferenced by this process when this routine
  126.  *    returns.
  127.  */
  128.  
  129. Buffer
  130. _bt_getroot(rel, access)
  131.     Relation rel;
  132.     int access;
  133. {
  134.     Buffer metabuf;
  135.     Buffer rootbuf;
  136.     Page rootpg;
  137.     BTPageOpaque rootopaque;
  138.     BlockNumber rootblkno;
  139.     BTMetaPageData *metad;
  140.  
  141.     metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
  142.     metad = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  143.  
  144.     /* if no root page initialized yet, do it */
  145.     if (metad->btm_root == P_NONE) {
  146.  
  147.     /* turn our read lock in for a write lock */
  148.     _bt_relbuf(rel, metabuf, BT_READ);
  149.     metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
  150.     metad = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  151.  
  152.     /*
  153.      *  Race condition:  if someone else initialized the metadata between
  154.      *  the time we released the read lock and acquired the write lock,
  155.      *  above, we want to avoid doing it again.
  156.      */
  157.  
  158.     if (metad->btm_root == P_NONE) {
  159.  
  160.         /*
  161.          *  Get, initialize, write, and leave a lock of the appropriate
  162.          *  type on the new root page.  Since this is the first page in
  163.          *  the tree, it's a leaf.
  164.          */
  165.  
  166.         rootbuf = _bt_getbuf(rel, P_NEW, BT_WRITE);
  167.         rootblkno = BufferGetBlockNumber(rootbuf);
  168.         rootpg = BufferGetPage(rootbuf, 0);
  169.         metad->btm_root = rootblkno;
  170.         _bt_pageinit(rootpg);
  171.         rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpg);
  172.         rootopaque->btpo_flags |= (BTP_LEAF | BTP_ROOT);
  173.         _bt_wrtnorelbuf(rel, rootbuf);
  174.  
  175.         /* swap write lock for read lock, if appropriate */
  176.         if (access != BT_WRITE) {
  177.         _bt_setpagelock(rel, rootblkno, BT_READ);
  178.         _bt_unsetpagelock(rel, rootblkno, BT_WRITE);
  179.         }
  180.  
  181.         /* okay, metadata is correct */
  182.         _bt_wrtbuf(rel, metabuf);
  183.     } else {
  184.  
  185.         /*
  186.          *  Metadata initialized by someone else.  In order to guarantee
  187.          *  no deadlocks, we have to release the metadata page and start
  188.          *  all over again.
  189.          */
  190.  
  191.         _bt_relbuf(rel, metabuf, BT_WRITE);
  192.         return (_bt_getroot(rel, access));
  193.     }
  194.     } else {
  195.     rootbuf = _bt_getbuf(rel, metad->btm_root, access);
  196.  
  197.     /* done with the meta page */
  198.     _bt_relbuf(rel, metabuf, BT_READ);
  199.     }
  200.  
  201.     /*
  202.      *  Race condition:  If the root page split between the time we looked
  203.      *  at the metadata page and got the root buffer, then we got the wrong
  204.      *  buffer.
  205.      */
  206.  
  207.     rootpg = BufferGetPage(rootbuf, 0);
  208.     rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpg);
  209.     if (!(rootopaque->btpo_flags & BTP_ROOT)) {
  210.  
  211.     /* it happened, try again */
  212.     _bt_relbuf(rel, rootbuf, access);
  213.     return (_bt_getroot(rel));
  214.     }
  215.  
  216.     /*
  217.      *  By here, we have a correct lock on the root block, its reference
  218.      *  count is correct, and we have no lock set on the metadata page.
  219.      *  Return the root block.
  220.      */
  221.  
  222.     return (rootbuf);
  223. }
  224.  
  225. /*
  226.  *  _bt_getbuf() -- Get a buffer by block number for read or write.
  227.  *
  228.  *    When this routine returns, the appropriate lock is set on the
  229.  *    requested buffer its reference count is correct.
  230.  */
  231.  
  232. Buffer
  233. _bt_getbuf(rel, blkno, access)
  234.     Relation rel;
  235.     BlockNumber blkno;
  236.     int access;
  237. {
  238.     Buffer buf;
  239.     Page page;
  240.  
  241.     /*
  242.      *  If we want a new block, we can't set a lock of the appropriate type
  243.      *  until we've instantiated the buffer.
  244.      */
  245.  
  246.     if (blkno != P_NEW) {
  247.     if (access == BT_WRITE)
  248.         _bt_setpagelock(rel, blkno, BT_WRITE);
  249.     else
  250.         _bt_setpagelock(rel, blkno, BT_READ);
  251.  
  252.     buf = ReadBuffer(rel, blkno);
  253.     } else {
  254.     buf = ReadBuffer(rel, blkno);
  255.     blkno = BufferGetBlockNumber(buf);
  256.     page = BufferGetPage(buf, 0);
  257.     _bt_pageinit(page);
  258.  
  259.     if (access == BT_WRITE)
  260.         _bt_setpagelock(rel, blkno, BT_WRITE);
  261.     else
  262.         _bt_setpagelock(rel, blkno, BT_READ);
  263.     }
  264.  
  265.     /* ref count and lock type are correct */
  266.     return (buf);
  267. }
  268.  
  269. /*
  270.  *  _bt_relbuf() -- release a locked buffer.
  271.  */
  272.  
  273. void
  274. _bt_relbuf(rel, buf, access)
  275.     Relation rel;
  276.     Buffer buf;
  277.     int access;
  278. {
  279.     BlockNumber blkno;
  280.  
  281.     blkno = BufferGetBlockNumber(buf);
  282.  
  283.     /* access had better be one of read or write */
  284.     if (access == BT_WRITE)
  285.     _bt_unsetpagelock(rel, blkno, BT_WRITE);
  286.     else
  287.     _bt_unsetpagelock(rel, blkno, BT_READ);
  288.  
  289.     ReleaseBuffer(buf);
  290. }
  291.  
  292. /*
  293.  *  _bt_wrtbuf() -- write a btree page to disk.
  294.  *
  295.  *    This routine releases the lock held on the buffer and our reference
  296.  *    to it.  It is an error to call _bt_wrtbuf() without a write lock
  297.  *    or a reference to the buffer.
  298.  */
  299.  
  300. void
  301. _bt_wrtbuf(rel, buf)
  302.     Relation rel;
  303.     Buffer buf;
  304. {
  305.     BlockNumber blkno;
  306.  
  307.     blkno = BufferGetBlockNumber(buf);
  308.     WriteBuffer(buf);
  309.     _bt_unsetpagelock(rel, blkno, BT_WRITE);
  310. }
  311.  
  312. /*
  313.  *  _bt_wrtnorelbuf() -- write a btree page to disk, but do not release
  314.  *             our reference or lock.
  315.  *
  316.  *    It is an error to call _bt_wrtnorelbuf() without a write lock
  317.  *    or a reference to the buffer.
  318.  */
  319.  
  320. void
  321. _bt_wrtnorelbuf(rel, buf)
  322.     Relation rel;
  323.     Buffer buf;
  324. {
  325.     BlockNumber blkno;
  326.  
  327.     blkno = BufferGetBlockNumber(buf);
  328.     WriteNoReleaseBuffer(buf);
  329. }
  330.  
  331. /*
  332.  *  _bt_pageinit() -- Initialize a new page.
  333.  */
  334.  
  335. _bt_pageinit(page)
  336.     Page page;
  337. {
  338.     /*
  339.      *  Cargo-cult programming -- don't really need this to be zero, but
  340.      *  creating new pages is an infrequent occurrence and it makes me feel
  341.      *  good when I know they're empty.
  342.      */
  343.  
  344.     bzero(page, BLCKSZ);
  345.  
  346.     PageInit(page, BLCKSZ, sizeof(BTPageOpaqueData));
  347. }
  348.  
  349. /*
  350.  *  _bt_metaproot() -- Change the root page of the btree.
  351.  *
  352.  *    Lehman and Yao require that the root page move around in order to
  353.  *    guarantee deadlock-free short-term, fine-granularity locking.  When
  354.  *    we split the root page, we record the new parent in the metadata page
  355.  *    for the relation.  This routine does the work.
  356.  *
  357.  *    No direct preconditions, but if you don't have the a write lock on
  358.  *    at least the old root page when you call this, you're making a big
  359.  *    mistake.  On exit, metapage data is correct and we no longer have
  360.  *    a reference to or lock on the metapage.
  361.  */
  362.  
  363. _bt_metaproot(rel, rootbknum)
  364.     Relation rel;
  365.     BlockNumber rootbknum;
  366. {
  367.     Buffer metabuf;
  368.     BTMetaPageData *metap;
  369.  
  370.     uint32    btm_magic;
  371.     uint32    btm_version;
  372.     BlockNumber    btm_root;
  373.     BlockNumber    btm_freelist;
  374.  
  375.     metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
  376.     metap = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  377.     metap->btm_root = rootbknum;
  378.     _bt_wrtbuf(rel, metabuf);
  379. }
  380.  
  381. /*
  382.  *  _bt_getstackbuf() -- Walk back up the tree one step, and find the item
  383.  *             we last looked at in the parent.
  384.  *
  385.  *    This is possible because we save a bit image of the last item
  386.  *    we looked at in the parent, and the update algorithm guarantees
  387.  *    that if items above us in the tree move, they only move right.
  388.  */
  389.  
  390. Buffer
  391. _bt_getstackbuf(rel, stack, access)
  392.     Relation rel;
  393.     BTStack stack;
  394.     int access;
  395. {
  396.     Buffer buf;
  397.     BlockNumber blkno;
  398.     OffsetIndex start, offind, maxoff;
  399.     OffsetIndex i;
  400.     Page page;
  401.     ItemId itemid;
  402.     BTItem item;
  403.     BTPageOpaque opaque;
  404.  
  405.     blkno = stack->bts_blkno;
  406.     buf = _bt_getbuf(rel, blkno, access);
  407.     page = BufferGetPage(buf, 0);
  408.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  409.     maxoff = PageGetMaxOffsetIndex(page);
  410.  
  411.     if (maxoff >= stack->bts_offset) {
  412.     itemid = PageGetItemId(page, stack->bts_offset);
  413.     item = (BTItem) PageGetItem(page, itemid);
  414.  
  415.     /* if the item is where we left it, we're done */
  416.     if (item->bti_oid == stack->bts_btitem->bti_oid)
  417.         return (buf);
  418.  
  419.     /* if the item has just moved right on this page, we're done */
  420.     for (i = stack->bts_offset + 1; i <= maxoff; i++) {
  421.         itemid = PageGetItemId(page, stack->bts_offset);
  422.         item = (BTItem) PageGetItem(page, itemid);
  423.  
  424.         /* if the item is where we left it, we're done */
  425.         if (item->bti_oid == stack->bts_btitem->bti_oid)
  426.         return (buf);
  427.     }
  428.     }
  429.  
  430.     /* by here, the item we're looking for moved right at least one page */
  431.     for (;;) {
  432.     if ((blkno = opaque->btpo_next) == P_NONE)
  433.         elog(FATAL, "my bits moved right off the end of the world!");
  434.  
  435.     _bt_relbuf(rel, buf, access);
  436.     buf = _bt_getbuf(rel, blkno, access);
  437.     page = BufferGetPage(buf, 0);
  438.     maxoff = PageGetMaxOffsetIndex(page);
  439.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  440.  
  441.     /* if we have a right sibling, step over the high key */
  442.     if (opaque->btpo_next != P_NONE)
  443.         start = 1;
  444.     else
  445.         start = 0;
  446.  
  447.     /* see if it's on this page */
  448.     for (offind = start; offind <= maxoff; offind++) {
  449.         itemid = PageGetItemId(page, offind);
  450.         item = (BTItem) PageGetItem(page, itemid);
  451.         if (item->bti_oid == stack->bts_btitem->bti_oid)
  452.         return (buf);
  453.     }
  454.     }
  455. }
  456.  
  457. _bt_setpagelock(rel, blkno, access)
  458.     Relation rel;
  459.     BlockNumber blkno;
  460.     int access;
  461. {
  462.     ItemPointerData iptr;
  463.  
  464.     if (!BuildingBtree) {
  465.     ItemPointerSet(&iptr, 0, blkno, 0, 1);
  466.  
  467.     if (access == BT_WRITE)
  468.         RelationSetSingleWLockPage(rel, 0, &iptr);
  469.     else
  470.         RelationSetSingleRLockPage(rel, 0, &iptr);
  471.     }
  472. }
  473.  
  474. _bt_unsetpagelock(rel, blkno, access)
  475.     Relation rel;
  476.     BlockNumber blkno;
  477.     int access;
  478. {
  479.     ItemPointerData iptr;
  480.  
  481.     if (!BuildingBtree) {
  482.     ItemPointerSet(&iptr, 0, blkno, 0, 1);
  483.  
  484.     if (access == BT_WRITE)
  485.         RelationUnsetSingleWLockPage(rel, 0, &iptr);
  486.     else
  487.         RelationUnsetSingleRLockPage(rel, 0, &iptr);
  488.     }
  489. }
  490.  
  491. void
  492. _bt_pagedel(rel, tid)
  493.     Relation rel;
  494.     ItemPointer tid;
  495. {
  496.     Buffer buf;
  497.     Page page;
  498.     BlockNumber blkno;
  499.     OffsetIndex offno;
  500.  
  501.     blkno = ItemPointerGetBlockNumber(tid);
  502.     offno = ItemPointerGetOffsetNumber(tid, 0);
  503.  
  504.     buf = _bt_getbuf(rel, blkno, BT_WRITE);
  505.     page = BufferGetPage(buf, 0);
  506.  
  507.     PageIndexTupleDelete(page, offno);
  508.  
  509.     /* write the buffer and release the lock */
  510.     _bt_wrtbuf(rel, buf);
  511. }
  512.